package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月16日
*时间：下午8:15:44
*/
public class Q437ii {
    /**
     * 二分查找
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length <= 0) {
            return 0;
        }
        int sum = 0;
        int max = -1;
        for (int i : pages) {
            if (max < i) {
                max = i;
            }
            sum += i;
        }
        int min = Integer.MAX_VALUE;
        while (max < sum) {
            int total = (max + sum) / 2;
            if (check(pages, k, total)) {
                if (min > total) {
                    min = total;
                }
                sum = total;
            } else {
                max = total + 1;
            }
        }
        return min;
    }

    private boolean check(int[] pages, int k, int total) {
        int sum = 0;
        int cnt = 0;
        for (int i : pages) {
            if (sum + i > total) {
                sum = i;
                cnt++;
            } else {
                sum += i;
            }
        }
        if (sum > 0) {
            cnt++;
        }
        return k >= cnt;
    }

    @Test
    public void testA() {
        // int[] pages = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        int[] pages = { 3, 2, 4 };
        System.out.println(copyBooks(pages, 2));
    }
}
